/*
题目: 字符串的前缀分数和
给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。

定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i] 的数目。

    例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。

注意：字符串视作它自身的一个前缀。

https://leetcode.cn/problems/sum-of-prefix-scores-of-strings
 */
public class SumPrefixScores {
    public static class Trie {
        int val;
        Trie[] children = null;

        public Trie(int val) {
            this.val = val;
            children = new Trie[26];
        }
    }
    Trie root ;

    public int[] sumPrefixScores(String[] words) {
        // 求所有前缀的 个数, 数据结构: 字典树
        root = new Trie(0);

        for (String word : words) {
            // 将元素插入字典树
            char[] cur = word.toCharArray();
            insert(cur);
        }

        // 遍历字典树
        int n = words.length;
        int[] src = new int[n];
        for (int i = 0; i < n; i++) {
            char[] cur = words[i].toCharArray();

            Trie head = root;
            for (char x : cur) {
                int pos = x - 'a';
                src[i] += head.children[pos].val;
                head = head.children[pos];
            }
        }
        return src;
    }

    // 将一个字符串插入字典树
    private void insert(char[] cur) {
        Trie head = root;
        for (int i = 0; i < cur.length; i ++) {
            int pos = cur[i] - 'a';
            if (head.children[pos] == null)
                head.children[pos] = new Trie(0);

            head.children[pos].val ++; // 前缀 ++
            head = head.children[pos]; // 向下走
        }
    }
}
